/*
 * (C) Copyright 2014-2016, by Dimitrios Michail
 *
 * JHeaps Library
 * 
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.jheaps.array

import org.jheaps.annotations.ConstantTime
import org.jheaps.annotations.LinearTime
import org.jheaps.annotations.LogarithmicTime
import org.jheaps.array.BinaryArrayBulkInsertWeakHeap
import java.io.Serializable
import kotlin.math.max

/**
 * An array based binary weak heap using bulk insertion. The heap is sorted
 * according to the [natural ordering][Comparable] of its keys, or by
 * a [Comparator] provided at heap creation time, depending on which
 * constructor is used.
 *
 *
 *
 * The implementation uses an array in order to store the elements and
 * automatically maintains the size of the array much like a
 * [java.util.Vector] does, providing amortized O(1) time cost for the
 * `insert` and amortized O(log(n)) for the `deleteMin` operation.
 * Operation `findMin`, is a worst-case O(1) operation.
 *
 *
 *
 * Constructing such a heap from an array of elements can be performed using the
 * method [.heapify] or [.heapify]
 * in linear time.
 *
 *
 *
 * Note that the ordering maintained by a binary heap, like any heap, and
 * whether or not an explicit comparator is provided, must be *consistent
 * with `equals`* if this heap is to correctly implement the
 * `Heap` interface. (See `Comparable` or `Comparator` for a
 * precise definition of *consistent with equals*.) This is so because
 * the `Heap` interface is defined in terms of the `equals`
 * operation, but a binary heap performs all key comparisons using its
 * `compareTo` (or `compare`) method, so two keys that are deemed
 * equal by this method are, from the standpoint of the binary heap, equal. The
 * behavior of a heap *is* well-defined even if its ordering is
 * inconsistent with `equals`; it just fails to obey the general contract
 * of the `Heap` interface.
 *
 *
 *
 * **Note that this implementation is not synchronized.** If
 * multiple threads access a heap concurrently, and at least one of the threads
 * modifies the heap structurally, it *must* be synchronized externally.
 * (A structural modification is any operation that adds or deletes one or more
 * elements or changing the key of some element.) This is typically accomplished
 * by synchronizing on some object that naturally encapsulates the heap.
 *
 * @param <K>
 * the type of keys maintained by this heap
 *
 * @author Dimitrios Michail
</K> */
open class BinaryArrayBulkInsertWeakHeap<K> @JvmOverloads constructor(
    comparator: Comparator<in K?>? = null,
    capacity: Int = BinaryArrayWeakHeap.DEFAULT_HEAP_CAPACITY
) : BinaryArrayWeakHeap<K>(comparator, capacity), Serializable {
    /**
     * The insertion buffer
     */
    protected var insertionBuffer: Array<K?>

    /**
     * Number of elements in the insertion buffer
     */
    protected var insertionBufferSize: Int = 0

    /**
     * Position of minimum in the insertion buffer
     */
    protected var insertionBufferMinPos: Int = 0

    /**
     * Constructs a new, empty heap, with a provided initial capacity using the
     * natural ordering of its keys.
     *
     *
     *
     * All keys inserted into the heap must implement the [Comparable]
     * interface. Furthermore, all such keys must be *mutually
     * comparable*: `k1.compareTo(k2)` must not throw a
     * `ClassCastException` for any keys `k1` and `k2` in the
     * heap. If the user attempts to put a key into the heap that violates this
     * constraint (for example, the user attempts to put a string key into a
     * heap whose keys are integers), the `insert(Object key)` call will
     * throw a `ClassCastException`.
     *
     *
     *
     * The initial capacity of the heap is provided by the user and is adjusted
     * automatically based on the sequence of insertions and deletions.
     *
     * @param capacity
     * the initial heap capacity
     */
    constructor(capacity: Int) : this(null, capacity)

    /**
     * Constructs a new, empty heap, with a provided initial capacity ordered
     * according to the given comparator.
     *
     *
     *
     * All keys inserted into the heap must be *mutually comparable* by
     * the given comparator: `comparator.compare(k1,
     * k2)` must not throw a `ClassCastException` for any keys `k1`
     * and `k2` in the heap. If the user attempts to put a key into the
     * heap that violates this constraint, the `insert(Object key)` call
     * will throw a `ClassCastException`.
     *
     *
     *
     * The initial capacity of the heap is provided by the user and is adjusted
     * automatically based on the sequence of insertions and deletions.
     *
     * @param comparator
     * the comparator that will be used to order this heap. If
     * `null`, the [natural ordering][Comparable] of
     * the keys will be used.
     * @param capacity
     * the initial heap capacity
     */
    /**
     * Constructs a new, empty heap, using the natural ordering of its keys.
     *
     *
     *
     * All keys inserted into the heap must implement the [Comparable]
     * interface. Furthermore, all such keys must be *mutually
     * comparable*: `k1.compareTo(k2)` must not throw a
     * `ClassCastException` for any keys `k1` and `k2` in the
     * heap. If the user attempts to put a key into the heap that violates this
     * constraint (for example, the user attempts to put a string key into a
     * heap whose keys are integers), the `insert(Object key)` call will
     * throw a `ClassCastException`.
     *
     *
     *
     * The initial capacity of the heap is
     * [BinaryArrayBulkInsertWeakHeap.DEFAULT_HEAP_CAPACITY] and adjusts
     * automatically based on the sequence of insertions and deletions.
     */
    /**
     * Constructs a new, empty heap, ordered according to the given comparator.
     *
     *
     *
     * All keys inserted into the heap must be *mutually comparable* by
     * the given comparator: `comparator.compare(k1,
     * k2)` must not throw a `ClassCastException` for any keys `k1`
     * and `k2` in the heap. If the user attempts to put a key into the
     * heap that violates this constraint, the `insert(Object key)` call
     * will throw a `ClassCastException`.
     *
     *
     *
     * The initial capacity of the heap is
     * [BinaryArrayBulkInsertWeakHeap.DEFAULT_HEAP_CAPACITY] and adjusts
     * automatically based on the sequence of insertions and deletions.
     *
     * @param comparator
     * the comparator that will be used to order this heap. If
     * `null`, the [natural ordering][Comparable] of
     * the keys will be used.
     */
    init {
        this.insertionBuffer = arrayOfNulls<Any>(INSERTION_BUFFER_CAPACITY) as Array<K?>
    }

    @get:ConstantTime
    override val isEmpty: Boolean
        get() {
            return size + insertionBufferSize == 0
        }

    /**
     * {@inheritDoc}
     */
    @ConstantTime
    override fun size(): Long {
        return size.toLong() + insertionBufferSize
    }

    /**
     * {@inheritDoc}
     */
    @ConstantTime
    override fun clear() {
        size = 0
        insertionBufferSize = 0
        insertionBufferMinPos = 0
    }

    /**
     * {@inheritDoc}
     */
    @ConstantTime
    override fun findMin(): K {
        if (size + insertionBufferSize == 0) {
            throw NoSuchElementException()
        }

        if (insertionBufferSize == 0) {
            return array[0]!!
        } else if (size == 0) {
            return insertionBuffer[insertionBufferMinPos]!!
        } else {
            val insertionBufferMin: K = insertionBuffer[insertionBufferMinPos]!!
            if (comparator == null) {
                if ((array[0] as Comparable<K?>) <= insertionBufferMin) {
                    return array[0]!!
                } else {
                    return insertionBufferMin
                }
            } else {
                return if (comparator.compare(array[0], insertionBufferMin) <= 0) {
                    array[0]!!
                } else {
                    insertionBufferMin
                }
            }
        }
    }

    /**
     * {@inheritDoc}
     */
    @ConstantTime(amortized = true)
    override fun insert(key: K) {
        if (key == null) {
            throw NullPointerException("Null keys not permitted")
        }

        // add in buffer
        insertionBuffer[insertionBufferSize++] = key

        if (isBulkInsertionBufferFull) {
            if (size + insertionBufferSize > array.size) {
                // first try to double size
                if (array.isEmpty()) {
                    ensureCapacity(1)
                } else {
                    ensureCapacity(2 * array.size)
                }
                // if not enough, set to requested size
                ensureCapacity(size + insertionBufferSize)
            }
            if (comparator == null) {
                bulkInsert()
            } else {
                bulkInsertWithComparator()
            }
        } else if (insertionBufferSize > 1) {
            // update minimum
            val insertionBufferMin: K = insertionBuffer[insertionBufferMinPos]!!
            if (comparator == null) {
                if ((key as Comparable<K?>) < insertionBufferMin) {
                    insertionBufferMinPos = insertionBufferSize - 1
                }
            } else {
                if (comparator.compare(key, insertionBufferMin) < 0) {
                    insertionBufferMinPos = insertionBufferSize - 1
                }
            }
        }
    }

    /**
     * {@inheritDoc}
     */
    @LogarithmicTime(amortized = true)
    override fun deleteMin(): K {
        if (size + insertionBufferSize == 0) {
            throw NoSuchElementException()
        }

        // where is the minimum
        var deleteFromInsertionBuffer: Boolean = false
        if (size == 0) {
            deleteFromInsertionBuffer = true
        } else if (insertionBufferSize > 0) {
            val arrayMin: K = array[0]!!
            val insertionBufferMin: K = insertionBuffer[insertionBufferMinPos]!!
            if (comparator == null) {
                if ((insertionBufferMin as Comparable<K>?)!! < arrayMin) {
                    deleteFromInsertionBuffer = true
                }
            } else {
                if (comparator.compare(insertionBufferMin, arrayMin) < 0) {
                    deleteFromInsertionBuffer = true
                }
            }
        }

        val result: K
        if (deleteFromInsertionBuffer) {
            result = insertionBuffer[insertionBufferMinPos]!!
            insertionBuffer[insertionBufferMinPos ] = insertionBuffer[insertionBufferSize - 1]
            insertionBuffer[insertionBufferSize - 1] = null
            insertionBufferSize--
            insertionBufferMinPos = 0
            if (comparator == null) {
                for (i in 1 until insertionBufferSize) {
                    if ((insertionBuffer[i] as Comparable<K>?)!!.compareTo(insertionBuffer[insertionBufferMinPos ]!!) < 0
                    ) {
                        insertionBufferMinPos = i
                    }
                }
            } else {
                for (i in 1 until insertionBufferSize) {
                    if (comparator.compare(insertionBuffer[i], insertionBuffer[insertionBufferMinPos]) < 0) {
                        insertionBufferMinPos = i
                    }
                }
            }
        } else {
            result = array[0]!!
            size--
            array[0] = array[size]
            array[size] = null
            if (size > 1) {
                if (comparator == null) {
                    fixdown(0)
                } else {
                    fixdownWithComparator(0)
                }
            }
            if (minCapacity <= array.size && 4 * size < array.size) {
                ensureCapacity(array.size / 2)
            }
        }

        return result
    }

    /**
     * Check if the bulk insertion buffer is full.
     *
     * @return true if the bulk insertion buffer is full, false otherwise
     */
    protected val isBulkInsertionBufferFull: Boolean
        get() {
            if (insertionBufferSize >= insertionBuffer.size) {
                return true
            }
            val sizeAsDouble: Double = size.toDouble() + insertionBufferSize
            return Math.getExponent(sizeAsDouble) + 3 >= insertionBuffer.size
        }

    /**
     * Bulk insert from insertion buffer into the weak heap.
     */
    protected fun bulkInsert() {
        if (insertionBufferSize == 0) {
            return
        }
        var right: Int = size + insertionBufferSize - 2
        var left: Int = max(size.toDouble(), (right / 2).toDouble()).toInt()
        while (insertionBufferSize > 0) {
            --insertionBufferSize
            array[size] = insertionBuffer[insertionBufferSize]
            insertionBuffer[insertionBufferSize]= null
            reverse!!.clear(size)
            ++size
        }
        while (right > left + 1) {
            left /= 2
            right /= 2
            for (j in left..right) {
                fixdown(j)
            }
        }
        if (left != 0) {
            val i: Int = dancestor(left)
            fixdown(i)
            fixup(i)
        }
        if (right != 0) {
            val i: Int = dancestor(right)
            fixdown(i)
            fixup(i)
        }
        insertionBufferMinPos = 0
    }

    /**
     * Bulk insert from insertion buffer into the weak heap.
     */
    protected fun bulkInsertWithComparator() {
        if (insertionBufferSize == 0) {
            return
        }
        var right: Int = size + insertionBufferSize - 2
        var left: Int = max(size.toDouble(), (right / 2).toDouble()).toInt()
        while (insertionBufferSize > 0) {
            --insertionBufferSize
            array[size] = insertionBuffer[insertionBufferSize]
            insertionBuffer[insertionBufferSize]= null
            reverse!!.clear(size)
            ++size
        }
        while (right > left + 1) {
            left /= 2
            right /= 2
            for (j in left..right) {
                fixdownWithComparator(j)
            }
        }
        if (left != 0) {
            val i: Int = dancestor(left)
            fixdownWithComparator(i)
            fixupWithComparator(i)
        }
        if (right != 0) {
            val i: Int = dancestor(right)
            fixdownWithComparator(i)
            fixupWithComparator(i)
        }
        insertionBufferMinPos = 0
    }

    companion object {
        
        /**
         * Insertion buffer capacity for integer size since we are using Java arrays
         * to store elements.
         */
        protected val INSERTION_BUFFER_CAPACITY: Int = 32 + 2

        /**
         * Create a heap from an array of elements. The elements of the array are
         * not destroyed. The method has linear time complexity.
         *
         * @param <K>
         * the type of keys maintained by the heap
         * @param array
         * an array of elements
         * @return a binary heap
         * @throws IllegalArgumentException
         * in case the array is null
        </K> */
        @JvmStatic
        @LinearTime
        fun <K> heapify(array: Array<K>?): BinaryArrayBulkInsertWeakHeap<K?> {
            if (array == null) {
                throw IllegalArgumentException("Array cannot be null")
            }
            if (array.isEmpty()) {
                return BinaryArrayBulkInsertWeakHeap()
            }

            val h: BinaryArrayBulkInsertWeakHeap<K?> = BinaryArrayBulkInsertWeakHeap(array.size)

            System.arraycopy(array, 0, h.array, 0, array.size)
            h.size = array.size

            for (j in h.size - 1 downTo 1) {
                h.join(h.dancestor(j), j)
            }

            return h
        }

        /**
         * Create a heap from an array of elements. The elements of the array are
         * not destroyed. The method has linear time complexity.
         *
         * @param <K>
         * the type of keys maintained by the heap
         * @param array
         * an array of elements
         * @param comparator
         * the comparator to use
         * @return a binary heap
         * @throws IllegalArgumentException
         * in case the array is null
        </K> */
        @LinearTime
        fun <K> heapify(array: Array<K>?, comparator: Comparator<in K?>?): BinaryArrayBulkInsertWeakHeap<K?> {
            if (array == null) {
                throw IllegalArgumentException("Array cannot be null")
            }
            if (array.size == 0) {
                return BinaryArrayBulkInsertWeakHeap(comparator)
            }

            val h: BinaryArrayBulkInsertWeakHeap<K?> = BinaryArrayBulkInsertWeakHeap(comparator, array.size)

            System.arraycopy(array, 0, h.array, 0, array.size)
            h.size = array.size

            for (j in h.size - 1 downTo 1) {
                h.joinWithComparator(h.dancestor(j), j)
            }

            return h
        }
    }
}
